As the characteristics of networks change, it is necessary to introduce new ways to control how network resources are allocated between end-users. Some such new mechanisms require all routers on a communication path to support a given new function (e.g. a specific ways of signalling path characterisation). The overall mechanism would not be effective unless every router on the network path supports the new function. This can only be achieved gradually, through incremental deployment. The default way to achieve this would be to upgrade every router in turn so they support the new function. However this can be a time-consuming, costly process.
Using a basic network model where all paths would have the same length “d”, and each node in the network would have the same probability “r” to provide the new function, the probability that an end-to-end path supports the new function is P=(r)^d.
Consider a path of 20 routers. At the start of the incremental deployment, if r=10%, then P=1.0 E−20: hardly any paths would support the new function. Even if r=90%, only about 12% of paths would support the function. Even if r=99%, still only 82% of paths support the function.
Any mechanism that speeds up incremental deployment can boost significantly the speed of adoption of a new functionality in a network.
We start by presenting the basic concept to facilitate the understanding of the mechanisms that are presented further on.
Packets
Data networks often split the data they carry into small units known as packets. Each communication protocol required to carry the information across the Internet adds a header that contains suitable information for the data exchange between the end hosts (usually a source host and a destination host) to be carried out appropriately. In the internet, one of the most common types of packet consists of a payload that contains the data generated by the application running at the source, encapsulated by a TCP header which ensures reliable delivery of the data, encapsulated again by an IP header, which ensures that the data reaches the destination host for which it is aimed. As a result, the TCP header contains a sequence number among other things, and the IP header contains the IP address of the destination host.
Distributed Bandwidth Sharing
Data travelling across the Internet follows a sequence of routers that constitutes the communication path from the source to the destination. Now, if many paths need to use a same router in the network, this router can get congested (packets experience delays for using that network). It would get overloaded and could fail if sources persist in sending traffic through that router. If sources still persist sending traffic around this bottleneck it could force more routers around to fail, and if the phenomenon keeps spreading, that could lead to a congestion collapse for the whole Internet—which occurred regularly in the mid-eighties.
The solution to that problem has been to ensure that sources take charge of the rate at which they send data over the Internet, by implementing congestion control mechanisms. Sources monitor path characterisation metrics to detect when the path their data is following is getting congested, in which case they react by reducing their throughput. They may slowly increase it again when there is no sign of the path being congested.
The typical path characterisation metrics sources monitor are the average round-trip time for the data path, the variance of the round-trip (jitter), and the level of congestion on the path, which is the primary parameter influencing the data rate adaptation of a source sending data over a congested path.
The congestion level can be signalled implicitly or explicitly. To this day, the most common option has been implicit signalling. Initially, routers would drop packets when they got completely saturated (which can always happen when a traffic burst cannot be accommodated in the buffer of the router)—this policy is called “Droptail”. An improvement has been proposed where congested routers monitor the average queue length in their buffer, and when the average queue is higher than a given threshold, the routers starts to drop packets with a probability which increases with the excess length of the queue over the threshold—this policy is called Random Early Detection (RED). It is widely used in today's internet because it allows sources to react more promptly to incipient congestion. Sources using TCP are able to detect losses, because a packet loss causes a gap in the sequence; whenever a source detects a loss, it halves its data rate, which alleviates the congestion on the router at the bottleneck.
Explicit Congestion Notification (ECN) [ECN] further improves on RED by using a two-bit ECN field in the IP header to signal congestion. It runs the same algorithm as RED, but instead of dropping a packet, it sets its ECN field to the Congestion Experienced (CE) codepoint.
The three other values of the two-bit ECN field are:                Non ECT, which signifies that the packet belongs to a flow that doesn't support ECN        ECT(0) and ECT(1), which signify that the packet belongs to a flow that supports ECN but that upstream routers haven't had to mark the packet.        
The ECN standard requires, the sender to echo any congestion mark signalled in the data; for instance, a TCP receiver sets the Echo Congestion Experienced (ECE) flag in the TCP header, which the TCP source interprets—for the purpose of its rate control—as if the packet has been dropped.
As the bandwidth required by applications and provided by networks keeps increasing, there is an ever more important need to develop suitable mechanisms for high-speed congestion control. It is now being argued that richer congestion information would help provide more robust congestion control mechanisms for the Internet [Stoics, Briscoe, Lachlan, Thommes].
Specific proposals have been put forward as to how such an encoding should be achieved. For instance the re-feedback proposal [Briscoe05c] suggests using a multi-bit congestion field which could effectively contain a floating-point representation of the congestion level, which each router on the path would update with its own local congestion level.
IP Tunnels
In the context of a data network, tunneling consists of encapsulating one protocol inside another protocol, and aims to improve the network service, for instance in terms of connectivity (it allows data to get across a network it couldn't get across otherwise), of security (the data is encrypted so it cannot be used if it is intercepted), etc.
A special case of IP tunnels are IP-in-IP tunnels where the original header is retained intact and is simply encapsulated in another standard IP header, at the entrance of the tunnel. The outer IP header source and destination addresses identify the “endpoints” of the tunnel while the inner header preserves the original source and destination addresses for the packet. As the packet traverses the tunnel, the outer header may be modified as the header of any other packet on the same path. When the packet reaches the other end of the tunnel, decapsulation occurs: the outer header is stripped off, the original header fields are updated if necessary, and the packet is forwarded to its originally-specified destination.
Tunnel End-Point Discovery (TED)
In order to use IP encapsulation tunnels it is necessary to establish the endpoints of the tunnel. This can be done manually by a user with explicit knowledge of the endpoints and sufficient permissions to be able to manipulate the routers appropriately. Alternatively it can be done using Tunnel Endpoint Discovery (TED) as described in the specifications of the IPsec protocol [IPsec]. Upon receiving a packet that needs to be encapsulated, the tunnel ingress will hold or drop this packet and create a TED packet with its own address as source address and the destination address of the initiating packet as destination address. The tunnel ingress then sends the packet as if it were a normal packet. When the packet reaches a node at the other end of the encapsulation region, this node declares itself as the egress node for the tunnel by sending back a packet with its address as the source and the address of the tunnel ingress as the destination.
EWMA
Finally, a classic way to monitor the evolution of a dynamic parameter is to use an Exponentially Weighted Moving Average (EWMA). We consider “xi” as the observed signal, “yi” as the resulting average, and “w” as the weight. Whenever a new value of the signal is observed, the average is updated according to the following algorithm:yi+1=(1−w)·yi+w·xi+1=yiw·(xi+1−yi)
The two parameters to be set are the weight, w, and the initial seed for the average, y0. The long term value of yi+1 doesn't depend on the initial seed y0.
In the context of binary signalling (which is the case when congestion is signalled by drops or by ECN marks), with mi the value of the binary mark, the algorithm can be written as:If mi+1=1: yi+1=yi+(1−yi)·w else: yi+1=(1−w)·yi Congestion Signalling and Traffic Tunneling
Congestion signalling has been well documented in many forms: whether it is by using an implicit signal [RED], an explicit binary signal [ECN] or an explicit multi-bit signal [ref]. The generic aspects of traffic tunneling have also been documented in standard documents, for instance “IP Encapsulation within IP” [RFC 2003] for IP-in-IP tunnels. [Briscoe07] reviews best practice for handling binary congestion marking in tunnels, by building on the recommendations available in the ECN and IPsec RFCs [ECN, IPsec] and in the IETF Internet Draft on “Explicit Congestion Marking in MPLS” [DBT07].